
/*!
    Copyright (C) 1991-2012 johnxguo GX.
    This file is a part of the "Heaven Engine".
*/

#ifndef __HEA_HEAPSORT_H_INCLUDED__
#define __HEA_HEAPSORT_H_INCLUDED__

#include "heaTypes.h"

namespace hea
{
namespace core
{
//! max heap
template<class T>
inline void heapsink( T* pHeap, s32 index, s32 mmax )
{
    s32 j = 0;
    while ((j = index << 1) <= mmax)
    {
        if (j + 1 <= mmax && pHeap[j] < pHeap[j+1])
        {
            j++;
        }
        if (pHeap[index] < pHeap[j])
        {
            math::swap(pHeap[index], pHeap[j]);
            index = j;
        }
        else
        {
            return;
        }
    }
}

//! heapsort
template<class T>
inline void heapsort( T* pArray, s32 size )
{
    T* pHeap = pArray - 1;
    s32 i = 0;
    for (i = size / 2; i > 0; --i)
    {
        heapsink(pHeap, i, size);
    }
    for (i = size; i > 1; --i)
    {
        math::swap(pHeap[1], pHeap[i]);
        heapsink(pHeap, 1, i - 1);
    }
}

}//end namespace core
}//end namespace hea

#endif